package psn.zjk.career.interview.algorithm;

import java.security.InvalidParameterException;

/**
 * @USER white
 * 查找第n大的数（快排变种）
 * @DATETIME 2021/1/19 18:49
 */
public class PickN {

    public int[] sort(int[] nums, int start, int end) {
        if (nums == null || nums.length == 0 || (start >= end)) {
            return nums;
        }
        int partition = partition(nums, start, end);
        sort(nums, start, partition - 1);
        sort(nums, partition + 1, end);
        return nums;
    }

    private int partition(int[] nums, int start, int end) {
        int base = start;
        int begin = base + 1;
        for (int i = begin; i <= end; i++) {
            if (nums[i] < nums[base]) {
                swap(nums, i, begin);
                begin++;
            }
        }
        swap(nums, begin - 1, base);
        return begin - 1;
    }

    private void swap(int[] nums, int i1, int i2) {
        int tmp = nums[i1];
        nums[i1] = nums[i2];
        nums[i2] = tmp;
    }

    public int pick(int[] nums, int m) {
        int n = m - 1;
        if (nums == null || nums.length < n) {
            throw new InvalidParameterException("");
        }
        int partition = partition(nums, 0, nums.length - 1);
        int left = 0;
        int right = nums.length - 1;
        while (partition != n) {
            partition = partition(nums, left, right);
            if (partition>n){
                right=partition-1;
            }else if (partition<n){
                left=partition+1;
            }
        }
        return nums[n];
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 4, 5, 11, 7, 6};
        System.out.println(new PickN().pick(nums, 7));


//        int[] numbers = {12, 15, 1, 18, 2, 35, 30, 11, 312};
//        Arrays.stream(numbers).forEach(num -> {
//            System.out.print(num + " ");
//        });
//        System.out.println();
//        //数组不建议用lambada
//        Arrays.stream(new PickN().sort(numbers,0,numbers.length-1)).forEach(num -> {
//            System.out.print(num + " ");
//        });
    }

}
